Uncompressed multimedia data requires considerable storage capacity and transmission bandwidth. In spite of the rapid progress in mass-storage density, processing speeds, and digital communication system performance, the demand for the data storage capacity and data-transmission bandwidth continues to outstrip the capabilities of available technologies. The recent growth of various multimedia-based applications, GISs (Geographic Information Systems), games, etc. have the increasing need for developing efficient ways for encoding and compressing images (particularly, elevation maps), data signals, Digital Terrain Elevation Data (DTED) and the like.
The prior art data compression methods/standards are either lossy or lossless. The compression ratio of conventional lossless methods (such as Huffman encoding, Arithmetic encoding, LZW (Lempel-Ziv-Welch) encoding) is relatively low and not high enough for providing efficient image and/or video compression, especially when the distribution of pixel values within the image is relatively flat. Thus, the images compressed by such methods usually cannot be displayed on mobile devices (such as cellular phones, PDAs (Personal Digital Assistants), etc.) due to the limited computation power and limited memory resources.
Earth surface images are similar to the most natural scene images, where the data or pixel values vary across a 2-D (dimensional) field. Usually, the earth surface contents change relatively slow within each elevation map, and the pixel intensity values do not significantly alter up and down in a small area of said each elevation map. If we represent an image in the spatial frequency domain, then the lower spatial frequency components of the image contain more information than the high frequency components, which usually relate to the less important image details and to noises within the image. In addition, humans are more receptive to the loss of higher spatial frequency components than to the loss of lower frequency components. Thus, for improving image compression, high frequency components of the image can be disregarded.
The dramatically increasing interest of people all over the world in GIS (Geographic Information System) applications (such as Google™ Earth, etc.), in particular presenting real-time/off-line earth surface maps (e.g., for navigation purposes), leads to the continuous need for developing efficient compression methods for elevating earth surface maps. In addition, GIS applications support receiving users' local queries over the elevation maps (e.g., determining the location of a specific point within each elevation map (user's point location query), approximating the height of said specific point, determining whether two points within the elevation map are located in a common field of view (user's visibility query), etc.). Such user's geometric queries can be performed efficiently over the compressed elevation maps and terrain images, and there is no need to uncompress them for answering such queries.
The prior art presents a number of terrain simplification methods/algorithms, such as combinatorial methods and lossless methods. The combinatorial methods for terrain simplification use a height (e.g., of an object within the terrain image) as an input (typically a rectangular grid of elevation data) and approximate it with a mesh of triangles of the terrain surface (this is also known as a triangulated irregular network (TIN)). The combinatorial methods attempt to minimize both the error and the number of triangles used for the approximation. These methods are often based on the 2-D triangulations (Delaunay triangulations) to create the triangular irregular networks. However, these methods are slow by nature due to the TIN terrain representation that require large computational resources, leading to the large error rate and to the low compression rate, and as a result, to a large file size and inefficient runtime.
The conventional combinatorial methods/algorithms for terrain simplification include Terra, GcTin, QSlim and others. The Terra algorithm is based on a greedy insertion algorithm with some optimizations to make it run faster. The input to the Terra algorithm is a height (e.g., of an object within the terrain image). It starts with the triangulation of the terrain surface, and then iteratively adds vertices according to which the input point has the greatest vertical error with respect to the approximating surface. After that, the retriangulation is performed by using the 2-D triangulation. Another combinatorial method, the GcTin method, employs an advancing-front technique for simplification of digitalized terrain models. The algorithm takes greedy cuts (bites) out of a closed polygon that bounds a connected component of the yet to be triangulated region, and then starts processing a large polygon, bounding the whole extent of the terrain to be triangulated, and works its way inward, performing at each step one of three basic operations: ear cutting, greedy biting, and edge splitting. One of the main advantages of the GcTin method is that it requires relatively low memory resources in addition to the memory resources required for processing an input height array. Still another combinatorial method, the QSlim method, is designed for simplifying all types of 3D (dimensional) surfaces, not just terrains. QSlim uses edge contraction for performing the terrain simplification, while employing a quadric error measurement for the efficiency and for visual fidelity. However, all these terrain simplification methods do not provide sufficient results and the compressed image has low geometric quality and large file size. In addition, MSE error (Mean Squared Error), MAE error (Mean Absolute Error) and RMS error (Root Mean Squared Error) of the compressed image are high, and the PSNR (Peak Signal-to-Noise Ratio) of said compressed image is relatively low, corresponding to high error rates.
The lossless compression methods for terrain simplification, such as JPEG-LS, JPEG2000-Lossless use DIP (Digital Image Processing), and they are implemented when it is important for the original and the decompressed image to be identical, or when no assumption can be made on whether certain deviations in the compressed image (compared to the original not compressed image) are uncritical. As a result, images compressed by means of the conventional lossless compression methods are large in size.
WO 2006/057477 presents a method for storing multipurpose geographic information, capable of integrating, storing, managing and using vector data (numerical map) and image, digital elevation model (DEM), three-dimensional (3D) point cloud data, and facility texture information. The method for storing multipurpose geographic information in a computing system includes the steps of: dividing geographic information data to be stored into minimum units; classifying the divided geographic information data into geometric information (geographic position information) and attribute information; and storing the geometric information (geographic position information) in a vector format and storing the attribute information in an attribute information linked to a vector. However, WO 2006/057477 does not teach performing preprocessing of an elevation map to be compressed, and does not teach implementing digital image processing methods for performing terrain simplification.
It is an object of the present invention to provide a terrain simplification method that is based on conventional digital image processing methods (which are originally designed for compressing natural scene images and not elevation maps), while significantly improving these methods to fit them for compressing said elevation maps and terrain images and to achieve an optimal visual and geometric quality of each compressed image.
It is still another object of the present invention to provide a terrain simplification method that is relatively fast, accurate, compact and efficient.
It is still another object of the present invention to provide a terrain simplification method that is relatively simple and robust, and therefore can be implemented on a large range of hardware, leading to dramatic improvements in runtime and compression efficiency.
It is still another object of the present invention to provide a terrain simplification method, in which a user can define various parameters for compressing each terrain image, such as the desirable size of the compressed terrain image, time for processing the terrain image, accuracy (quality) of said processing, acceptable error rate, etc.
It is still another object of the present invention to provide a terrain simplification method, which can be further employed on mobile devices (such as cellular phones, PDAs, etc.) that have relatively low computational power.
It is a further object of the present invention to provide a terrain simplification method for use in various applications, such as mapping applications, games, map-warehouse-storage applications, and many others.
It is still a further object of the present invention to provide a novel file format for compressing elevation maps.
It is still a further object of the present invention to provide a terrain simplification method, which is user friendly.
Other objects and advantages of the invention will become apparent as the description proceeds.